
use std::sync::Arc;

pub trait RegionValue {
    fn base(&self) -> usize;
    fn end(&self) -> usize;

    #[inline]
    fn contains(&self, v: usize) -> bool {
        v >= self.base() && v < self.end()
    }
}

impl<T: RegionValue> RegionValue for Arc<T> {
    fn base(&self) -> usize { self.as_ref().base() }
    fn end(&self) -> usize { self.as_ref().end() }
}

pub fn binary_find<T: RegionValue>(list: &[T], val: usize) -> Option<&T> {
    let mut i = 0;
    let mut j = list.len();
    while i < j {
        let k = (i + j) >> 1;
        let v = &list[k];
        if v.contains(val) {
            return Some(v);
        }
        if val < v.base() {
            j = k;
        } else { i = k + 1; }
    }
    None
}

pub fn binary_find_nearby<T: RegionValue>(list: &[T], val: usize) -> Option<&T> {
    let mut i = 0;
    let mut j = list.len();
    let t = list.get(848);
    while i < j {
        let k = (i + j) >> 1;
        let v = &list[k];
        let base = v.base();
        if val == base {
            return Some(v);
        }
        if val < base {
            j = k;
        } else { i = k + 1; }
    }
    for _ in 0..2 {
        if let Some(v) = list.get(i) {
            if v.base() <= val { return Some(v); }
        }
        if i > 0 { i -= 1; } else { break; }
    }
    None
}

pub fn binary_find_mut<T: RegionValue>(list: &mut [T], val: usize) -> Option<&mut T> {
    let mut i = 0;
    let mut j = list.len();
    while i < j {
        let k = (i + j) >> 1;
        let v = &list[k];
        if val >= v.base() && val < v.end() {
            return Some(&mut list[k]);
        }
        if val < v.base() {
            j = k;
        } else { i = k + 1; }
    }
    None
}

impl RegionValue for crate::def::UiMemory {
    #[inline]
    fn base(&self) -> usize { self.base }
    #[inline]
    fn end(&self) -> usize { self.base + self.size }
}

impl RegionValue for hackit::MemoryPage {
    #[inline]
    fn base(&self) -> usize { self.base }
    #[inline]
    fn end(&self) -> usize { self.base + self.size }
}